import java.util.HashSet;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow){
                ListNode index1 = fast;
                ListNode index2 = head;

                while (index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

    //投机取巧法：HashSet
    public ListNode detectCycle2(ListNode head) {
        HashSet<ListNode> hashSet = new HashSet<>();
        ListNode cur = new ListNode(0);
        cur.next = head;

        while (hashSet.add(cur) != false) {
            if (cur == null) {
                return null;
            }
            cur = cur.next;
        }
        return cur;
    }

}